package org.mianshi.maoyan;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * 参考文章：https://blog.csdn.net/My_Jobs/article/details/43451187
 */

public class 二叉树遍历 {
    // 定义二叉树节点
    public static class TreeNode {
        int value;          // 节点值
        TreeNode left;      // 左子节点
        TreeNode right;     // 右子节点

        // 构造函数
        public TreeNode(int value) {
            this.value = value;
            this.left = null;
            this.right = null;
        }

        // 插入节点（辅助方法）
//        public void insert(int newValue) {
//            if (newValue < this.value) {
//                if (this.left == null) {
//                    this.left = new TreeNode(newValue);
//                } else {
//                    this.left.insert(newValue);
//                }
//            } else {
//                if (this.right == null) {
//                    this.right = new TreeNode(newValue);
//                } else {
//                    this.right.insert(newValue);
//                }
//            }
//        }


        //前序遍历
        public static void beforeSort(TreeNode node, List<Integer> sortList) {
            if (node != null) {
                sortList.add(node.value);
                beforeSort(node.left, sortList);
                beforeSort(node.right, sortList);
            }
        }

        //中序遍历
        public static void inSort(TreeNode node, List<Integer> sortList) {
            if (node != null) {
                inSort(node.left, sortList);
                sortList.add(node.value);
                inSort(node.right, sortList);
            }
        }


        //后序遍历
        public static void afterSort(TreeNode node, List<Integer> sortList) {
            if (node != null) {
                afterSort(node.left, sortList);
                afterSort(node.right, sortList);
                sortList.add(node.value);
            }
        }

        //层序遍历
        public static void cengSort(TreeNode root,List<Integer> sortList){
            LinkedList<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            while (!queue.isEmpty()){
                TreeNode pop = queue.pop();
                sortList.add(pop.value);
                if (pop.left!=null){
                    queue.offer(pop.left);
                }
                if (pop.right!=null){
                    queue.offer(pop.right);
                }
            }

        }


        //深度遍历
        public static void deepSort(TreeNode root,List<Integer> sortList){
            LinkedList<TreeNode> stack = new LinkedList<>();
            stack.push(root);
            while (!stack.isEmpty()){
                TreeNode pop = stack.pop();
                sortList.add(pop.value);
                if (pop.right!=null){
                    stack.push(pop.right);
                }
                if (pop.left!=null){
                    stack.push(pop.left);
                }
            }

        }

    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);  // 创建根节点
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.right.right = new TreeNode(6);
        root.left.right.left = new TreeNode(7);
        root.left.right.right = new TreeNode(8);
        List<Integer> beforeSortList = new ArrayList<>();
        TreeNode.beforeSort(root,beforeSortList);
        beforeSortList.forEach(System.out::print);

        List<Integer> inSortList = new ArrayList<>();
        TreeNode.inSort(root,inSortList);
        System.out.println("...........");
        inSortList.forEach(System.out::print);

        List<Integer> afterSortlist = new ArrayList<>();
        TreeNode.afterSort(root,afterSortlist);
        System.out.println("...........");
        afterSortlist.forEach(System.out::print);


        //层序遍历，也是广度优先
        System.out.println("...........");
        List<Integer> cengSortList = new ArrayList<>();
        TreeNode.cengSort(root,cengSortList);
        cengSortList.forEach(System.out::print);



        //深度优先
        System.out.println("...........");
        List<Integer> deepSortList = new ArrayList<>();
        TreeNode.deepSort(root,deepSortList);
        deepSortList.forEach(System.out::print);





    }


}
